ループ防止のためのリンク状態ハンドシェークの方法および装置

专利摘要:
リンク状態プロトコルによって制御される通信ネットワークのネットワーク・ノードはネットワークトポロジの変化に関する情報を含むメッセージを受信するネットワーク・インタフェースを含む。ノードは処理ユニットを含み、処理ユニットが行うのは、ネットワークの少なくとも１つの隣接ノードへのトラフィック転送のネットワーク・インタフェースにおけるブロックと、隣接ノードとのトポロジ変化に関する合意と、メモリのトポロジに関する情報と同じトポロジに関する情報を隣接ノードが有する場合のトラフィック転送ブロックの解除とである。リンク状態プロトコルによって制御される複数のネットワーク・ノードを有するネットワークのネットワーク・ノードが有する過渡のループ防止方法はネットワークトポロジの変化に関する情報を含むメッセージをネットワーク・インタフェースで受信するステップを含む。ネットワーク・インタフェースでネットワークの各隣接ノードへのトラフィック転送を処理ユニットによりブロックするステップを含む。隣接ノードとトポロジ変化に関し処理ユニットにより合意するステップを含む。メモリに格納したトポロジに関する情報と同じトポロジに関する情報を隣接ノードが有する場合、トラフィック転送ブロックを解除するステップを含む。
公开号:JP2011515057A
申请号:JP2010550279
申请日:2009-03-10
公开日:2011-05-12
发明作者:ジャノス ファーカス，
申请人:テレフオンアクチーボラゲット エル エム エリクソン（パブル）；
IPC主号:H04L12-56

专利说明:

[0001] 本発明はパケット交換通信ネットワークにおける過渡のループの防止に関するものである。]
背景技術

[0002] ここで読者に紹介しようとするのは、本発明の種々の態様に関係しうる多様な技術態様である。以下の考察で提供しようとするのは、本発明のより良い理解を容易にする情報である。従って理解すべきは、以下の考察における記述はこの観点で読むべきであり、従来技術の容認としてではないことである。]
[0003] 今日、ＩＰおよびイーサネット（登録商標）・ネットワークのようなパケット交換ネットワークのより速いネットワーク収束への増大するニーズがあるのは、これらのネットワークが伝送する実時間トラフィック量の増大に起因する。ＩＰネットワークの高速障害処理を提供するために、種々のＩＰ高速再ルーティング（ＩＰＦＲＲ、IP Fast Re-Route）技術が導入されている。ユーザトラフィックは非常に速くバックアップ経路に再方向指定されるが、ＩＰネットワークに適用するリンク状態制御プロトコルはそれほど速く収束しない。したがって、所謂マイクロループがトポロジの過渡期に発生することがあり、これは回避しなければならない。]
[0004] リンク状態制御プロトコルをイーサネット・ネットワークにも適用することが最近提案され；アーキテクチャがＩＥＥＥ８０２．１ａｑ最短経路ブリッジング（ＩＥＥＥ８０２．１ａｑバーチャルブリッジローカルエリアネットワーク−修正９：最短経路ブリッジング、ドラフトＤ０．４、２００８年２月１９日）で仕様化されつつある。偶発的なループはループ化マルチキャストまたはブロードキャストフレームの増加に起因してネットワークメルトダウンの原因となりうるので、イーサネット・ネットワークにおけるループの防止は必須のものである。ＩＰとは対照的にイーサネットフレームのヘッダにＴＴＬフィールドがないので、従ってループのために増加するフレームはネットワークから消すことができない。]
[0005] イーサネット・ネットワーク及びＩＰＦＲＲネットワークにおけるリンク状態制御プロトコルの適用は有効なループ防止機構の必要性を高める。]
[0006] また逆経路転送チェック（ＲＰＦＣ、Reverse Path Forwarding Check）とも称する入力チェックがＳＰＢにおいてループを処理するために提案されている。しかしながら入力チェックは全ての起こりうるループを除去せず、一時的なループの可能性を低減するのみである。即ち２，３の例により示すように入力チェックを適用するにもかかわらず、偶発ループは発生しうる。]
[0007] ＩＰＦＲＲにおけるループ防止には種々の提案がある。しかし、これらの方法のそれぞれには重大な欠点がある。これらの方法は遅いか、トンネリング（tunneling）を適用するか、又は、制御プレーン外プロトコル（例えばＮＴＰ）などを要求するかの何れかである。したがって、明白な解決策は提案されていない。]
[0008] 本発明が関係するのはネットワークにおける過渡のループ防止であり、ネットワークトポロジの変化に関する情報を含むメッセージをノードが受信する場合、ネットワーク・ノードによるトラフィック転送のブロックに基づきリンク状態プロトコルによりネットワークを制御する。このトラフィック転送のブロックは相互に独立に各隣接ノードに対して確立され、物理的ネットワークトポロジに関して２つの隣接ノードが全く同じ見解を有することを２つの隣接ノードが合意するまで、即ち２つの隣接ノードの双方が物理ネットワークトポロジに関する全く同じ情報を受信した、例えば双方が物理トポロジの全ての変化に関する情報を受信したことを双方が合意するまで、２つの隣接ノード間リンクに関してブロックを維持する。隣接ノード間での合意の後、隣接ノード間リンクに関するトラフィック転送のブロックが解除される。]
[0009] 従ってネットワークの過渡期において発生しうる全ての起こりうるループの発生を防止する。さらに、合意、即ち、隣接ノード間のトポロジ見解の同期は相互に独立であり、従ってリンクブロック時間を最小化し、ループフリー収束を高速化する。]
図面の簡単な説明

[0010] 添付する図面において、本発明の好ましい実施形態および本発明を実行する好ましい方法を示す。
トポロジ変化に関する情報を有するメッセージを受信する場合の本発明のフローチャートである。
隣接ノードから同期要求メッセージを受信する場合の本発明のフローチャートである。
ネットワークトポロジの例である。
図３のネットワークトポロジについて最初に通知を受けるノードを示す。
リンク状態ハンドシェークプロトコルの動作例に関してその経路をブロックするノードを示す。
変化例を認識する追加ノードを示す。
変化例を認識するさらに多くのノードを示す。
変化例を認識する全てのノードを示す。
全ノードの更新例を示す。
入力チェックを適用しても発生するＩＳ−ＩＳベースＳＰＢにおける過渡のループを示す。
本発明のＳＰＢシナリオのループ防止を示す。
本発明のノードのブロック図である。] 図３
実施例

[0011] 以下で参照する図面において、同一の参照番号がそれらの図面を通じて類似または同一の部分を参照するために用いられる。まず図１２を参照して、リンク状態プロトコルによって制御される通信ネットワーク１０のネットワーク・ノード１２について説明する。図１２で詳細に示すノード１２はネットワーク・インタフェース１４を含み、ネットワーク・インタフェースはネットワーク１０のトポロジ変化に関する情報を含むメッセージを受信する。ノード１２は処理ユニット１６を含み、処理ユニットが行うのは、ネットワーク１０の少なくとも１つの隣接ノード２０へのトラフィック転送のネットワーク・インタフェース１４でのブロックと、隣接ノード２０とのトポロジ変化に関する合意と、メモリ１８の物理トポロジに関する情報と同じ物理トポロジに関する情報を隣接ノード２０が有する場合のトラフィック転送ブロックの解除とである。物理トポロジは全ネットワーク・ノードおよび全ネットワーク・ノード間の全接続を含む。リンク状態制御プロトコルはネットワークで使用され、制御プロトコルエンティティのインスタンスは各ネットワーク・ノードで動作する。リンク状態制御プロトコルは各ネットワーク・ノードにおける物理トポロジに関する情報を維持する。リンク状態制御プロトコルはネットワーク・ノード間のデータメッセージの転送経路を決定する。イーサネット・ネットワークで使用する転送経路は常にループフリーであるべきである所謂アクティブトポロジを含む。従来のイーサネット・ネットワークでは、アクティブトポロジは典型的に高速スパニング・ツリー・プロトコル（ＲＳＴＰ、Rapid Spanning Tree Protocol）により制御するスパニングツリーである。スパニングツリーは全ての物理接続を含まないが、幾つかの冗長なスパニングツリーをインアクティブにし、ループを回避する。ＲＳＴＰによりアクティブに保つ接続はスパニングツリーであるアクティブトポロジを形成する。ＭＳＴＰおよびＳＰＢは複数のアクティブトポロジ、即ち複数のツリーを処理することができる。] 図１２
[0012] ネットワーク・インタフェース１４はトポロジへの変化に関する情報を含む通知を別の隣接ノード２２から受信することができる。処理ユニット１６がネットワーク・インタフェース１４の少なくとも１つのポートでブロックすることができるのは、変化により影響を受ける少なくともアクティブトポロジまたは転送経路である。ネットワーク・インタフェース１４は通知に関する情報を含む同期要求を少なくとも１つのポートで隣接ノード２０に送信することができる。処理ユニット１６は隣接ノード２０が通知を受信したかどうかを検証することができる。通知におけるトポロジ情報に従って隣接ノード２０がトポロジを更新したことを示す同期確認を、ネットワーク・インタフェース１４は同期要求が送信された隣接ノード２０から受信することができる。同期の目的が保証するのは、隣接ノードがネットワーク物理トポロジに関して全く同じ見解（view）を有することである。上述したように、隣接ノードの両方が互いに物理トポロジに関する情報の全部分を受信した、即ち、全く同じ通知セットを有することを検証することによってこの保証を実現することができる。これに対する代替は、ネットワーク物理トポロジを記述する全く同じトポロジ・データベースを隣接ノードが共に有することを検証することである。このために、隣接ノードはそのトポロジ・データベースのダイジェスト情報（物理トポロジを記述するデータベースの一部または例えば全ての受信通知を格納した全トポロジ・データベース）を交換し、当該ダイジェスト情報に基づき隣接ノードを同期させることができる。ダイジェスト情報は例えばトポロジ・データベースに基づいて用意される固有のハッシュまたはＣＲＣでありうる。]
[0013] ネットワーク・インタフェース１４はノードＩＤおよび通知シーケンス番号を有する同期確認を受信することができる。ネットワーク・インタフェース１４は同期要求を受信することができる。処理ユニット１６は通知が受信され、かつ、同期要求が送信されるように処理されたかを検証することができる。ネットワーク・インタフェース１４は同期確認を送信することができる。通知がトポロジ変化情報を有する場合ネットワーク・インタフェース１４が有することができるのは、ポート毎に各リンク状態ＰＤＵに設定するＩＳ−ＩＳ送信ルーティング・メッセージ・フラグおよびポートブロックに関するフラグである。トポロジ・データベースのダイジェスト情報を有するか、またはノードＩＤおよび通知シーケンス番号を有する他に、同期要求メッセージ・フラグおよび同期確認メッセージ・フラグを有するＲＳＴＰ／ＭＳＴＰのＢＰＤＵが存在しうる。]
[0014] 本発明が関係するのはネットワーク１０が持つネットワーク・ノード１２の過渡のループを防止する方法であり、ネットワークは図１および図２に示すリンク状態プロトコルによって制御される複数のネットワーク・ノード１２を有する。本方法は以下のステップを有する。ステップＳ１１において、ネットワーク・インタフェース１４は、ネットワーク１０のトポロジ変化に関する情報を含むメッセージを受信する。ステップＳ１２において、処理ユニット１６は、ネットワーク・インタフェース１４でネットワーク１０の各隣接ノード２０へのトラフィック転送をブロックする。トポロジ変化に関して処理ユニット１６によって隣接ノード２０と合意するステップが存在する。隣接ノード２０がトポロジに関する情報を有し、当該情報がメモリ１８に格納したトポロジに関する情報と同じである、即ち隣接ノード２０がトポロジに関して同じ見解を有する場合、ステップＳ１６においてトラフィック転送ブロックが解除される。ステップＳ１７において、ブロックされたインタフェース２０がまだ存在するかどうかがチェックされる。] 図１ 図２
[0015] メッセージを受信するステップＳ１１が含むことができるのは、トポロジへの変化に関する情報を含む通知を別の隣接ノード２２からネットワーク・インタフェース１４で受信するステップである。ブロックステップＳ１２が含むことができるのは、変化により影響を受ける少なくともアクティブトポロジまたは転送経路をネットワーク・インタフェース１４でブロックするステップである。また、メモリ１８のトポロジと同じトポロジを隣接ノード２０がそのメモリ１８に有することを隣接ノード２０が合意するまで、ブロックを維持するステップが実行されてもよい。]
[0016] 合意ステップは、通知またはトポロジ・データベースに関する情報を含む同期要求の少なくとも１つのポートで他の隣接ノード２２への送信ステップＳ１３を含んでもよい。また、合意ステップは、隣接ノード２０が同じ通知（単数または複数）を受信した、即ち全く同じトポロジ・データベースを有すかどうかを検証する検証ステップを含んでもよい。検証ステップは、同期要求を送信した隣接ノード２０からの通知のトポロジ情報により隣接ノード２０がトポロジを更新したことを示す同期確認を受信する受信ステップＳ１４を含んでもよい。同期確認受信ステップＳ１４は、ノードＩＤおよび通知シーケンス番号を有する同期確認の受信またはトポロジ・データベースに関するダイジェスト情報を有する同期確認を受信する受信ステップを含んでもよい。検証ステップは、隣接ノード２０に送信した全く同じ情報部分に関する同期要求を受信する受信ステップＳ１５を含んでもよい。即ち、受信された同期要求は、以前に隣接ノード２０に送信した同期要求と全く同じノードＩＤおよびシーケンス番号またはダイジェスト情報を有してもよい。]
[0017] 図２により詳細に示すように、ステップＳ２１において、ネットワーク・インタフェース１４は、同期要求を受信する。ステップＳ２２において、処理ユニット１６は、通知が受信され、処理された、または同期要求を送信した同じトポロジ・データベースに関するダイジェスト情報を有するかどうかを検証する。ステップＳ２３において、全く同じ情報部分に関する同期要求が隣接ノード２０に送信されたかどうかがチェックされる。ステップＳ２４において、ネットワーク・インタフェース１４は、同期確認を送信する。ステップＳ２５において、ポートがブロックされていれば、ポートブロックが解除される。] 図２
[0018] 各ＩＳ−ＩＳリンク状態ＰＤＵのＩＳ−ＩＳ送信ルーティング・メッセージ・フラグを構成するステップが各ネットワーク・インタフェース１４で実行されてもよい。トポロジ変化情報を含む通知受信におけるポートブロックに関するフラグを設定するステップＳ１２が実行されてもよい。或いは、ＲＳＴＰ／ＭＳＴＰのＢＰＤＵが存在してもよく、ＲＳＴＰ／ＭＳＴＰのＢＰＤＵは同期要求メッセージ・フラグと、同期確認メッセージ・フラグと、例えばトポロジ・データベースのダイジェスト情報またはノードＩＤおよびシーケンス番号を示す、同期を要求する情報の記述とを有する。メモリ１８に格納したトポロジの少なくとも一部のダイジェスト情報に関する隣接ノード２０との合意ステップが実行されてもよい。合意ステップでは、ＣＲＣまたはハッシュを使用するステップが実行されてもよい。]
[0019] 物理トポロジが安定である、即ち物理トポロジに変化がない場合、イーサネット・ネットワークのアクティブトポロジに、またはＩＰネットワークの転送ツリーにループは存在しない。即ちループが発生しうるのは、ネットワーク１０の変化、例えば故障の発生または再構成による転送トポロジの再構成中においてのみであるが、制御プレーンの更新前後には何れもループは存在しない。したがって、ループ防止はトポロジの過渡期に動作しなければならない。]
[0020] さらに、リンク状態制御プロトコルの場合の偶発的なループの主な理由は、非同期、即ち異なる時間および予測できない変化通知順序において、ネットワーク・ノード１２が変化（単数または複数）に気づくことである。即ち、偶発的なループの主な理由は、ネットワーク１０のトポロジに関してノード１２が一貫性のない見解を有することである。]
[0021] 物理トポロジの変化にかかわらず本発明の動作では、一時的または過渡のループは存在しない。本発明は、ノード１２がトポロジ変化に気づけば、ネットワーク・ノード１２で一時的に転送をブロックする。次いでノード１２はその隣接するノードの１つずつと、互いに独立してハンドシェーク・ネゴシエーション技術を開始する。隣接ノードが共にネットワーク１０の物理トポロジに関して同じ情報を有すれば、リンクは再びブロックを解除される。隣接ノードは直近のトポロジ変化に関し、またはハンドシェーク技術における物理トポロジのダイジェスト情報に関しての何れかに合意する。したがって、トポロジに関して異なる見解を有する隣接ノード間でリンクを使用することは生じえない。このような隣接ノード間のリンクブロックにより、ループが発生しうる前にあらゆる起こりうるループが切断される。]
[0022] 全ての安定な転送トポロジ、即ちイーサネット・ネットワークのアクティブトポロジまたはＩＰネットワークのルーティング登録により考案する転送ツリーはループフリーである。即ち、変化前に制御プロトコルにより設定する転送トポロジまたは変化後の転送トポロジの何れにもループは存在しない。トポロジの過渡期に適用する適切な切断によりネットワーク１０からループを除去することができる。リンク状態制御プロトコルに対し本発明で提案するハンドシェークベースのループ切断機構を以下で詳細に説明する。]
[0023] リンク状態プロトコルは周期的なハローメッセージを適用し、ノード１２の隣接ノードを発見し、接続性を監視する。ＯＳＰＦの場合のリンク状態通知（ＬＳＡ、Link State Advertisement）メッセージまたはＩＳ−ＩＳの場合のリンク状態プロトコル・データ・ユニット（ＬＳＰ、Link State Protocol）を多量に流すことにより、各ノード１２はその隣接情報を通知する。これらの通知は送信ノード１２のＩＤおよびシーケンス番号によって識別される。したがって、ノード１２が所定のノード１２から直近の通知を受信したか否かを容易に検証することができる。ネットワーク・ノード１２はネットワーク１０の物理トポロジに関するデータベースを構築し、維持し、このトポロジ・データベースに基づき転送経路を計算する。従って全ノード１２がトポロジに関して同じ見解を有すれば、その場合全ノード１２は全く同じ転送経路を計算し、従ってループは発生しえない。データベースのダイジェスト情報、例えばＣＲＣまたはハッシュの交換により、２つのノードのトポロジ・データベースが同一であるかをまた検証することができる。]
[0024] 図１は、ノード１２によってリンク状態通知が受信された場合に、提案するループ防止方法の動作を示す。リンク状態通知がただ旧情報の更新であれば、その場合ループ防止機構にとり為すべきことはない。これに反し通知がトポロジ変化情報を含めば、その場合受信ノード１２はそのポート全てをブロックしなければならない。従って転送トポロジにブロックが発生しえ、このようにしてネットワーク１０の偶発的なループの発生を防止する。ポートブロックは全ポートのブロックまたは変化により影響を受けるアクティブトポロジのブロックのみを意味しうる。例えばＳＰＢの場合、複数の最短経路ツリー（ＳＰＴ、Shortest Path Trees）の構成が存在し、通知が属すツリーのみのブロックで十分である。] 図１
[0025] ポートブロック後、直近に受信した通知（単数または複数）、即ちノードＩＤおよびシーケンス番号に関する情報を含むか、またはトポロジ・データベースのダイジェスト情報を含むか何れかの同期要求（ＳｙｎｃＲｅｑ、Synchronization Request）を各ポート上の隣接ノード２０に送信する。当該要求は一束の通知であってもよく、即ちＳｙｎｃＲｅｑメッセージは複数のノードＩＤおよび対応するシーケンス番号を含んでもよい。]
[0026] 同期を要求した同じＬＳＡ（ＬＳＰ）または同じダイジェスト情報に関する同期確認（ＳｙｎＡｃｋ、Synchronization Acknowledgement）を隣接ノード２０から受信するまで、ポートをブロックする。ＳｙｎＡｃｋはまた確認するノードＩＤおよび通知のシーケンス番号を含むか、またはダイジェスト情報を含む。要求を受信したノード１２がまた問題の通知を受信し、新規物理トポロジにより転送トポロジを更新したとすれば、即ち同じトポロジ・データベースを有すれば、確認を送出する。]
[0027] その特定の隣接ノードがトポロジ変化を確認するまで、隣接ノード２０への要求ノード１２での切断が存在する。]
[0028] 図２が示すのは、ノード１２により同期要求を受信する場合のリンク状態ループ防止ハンドシェーク機構の動作である。まず同期要求を送信したのと全く同じ通知（単数または複数）を受信し、処理したかを検証しなければならない。なお、リンク状態ハンドシェーク方法の実装に応じて同期処理中に複数の通知が束ねられる。] 図２
[0029] 同じ通知（単数または複数）を受信、処理すれば、その場合通知（単数または複数）のＩＤ（単数または複数）を含むか、またはダイジェスト情報を含む同期確認メッセージを隣接ノードに送信し、ポートを以前にブロックしていれば、ポートをブロック解除する。]
[0030] なお、２つの隣接ノード２０が同時（または事実上同時）に全く同じ通知を受信することがある。その場合両ノード２０は同期要求の送信によりハンドシェーク機構を開始する。この状況を処理する２つのオプションが存在する：
ａ）両ノードがリンクをブロック、要求を送信、確認を送信、確認を他のノード側から受信、リンクをブロック解除、
ｂ）両隣接ノードが同じトポロジ情報を有するので、隣接ノードから受信する全く同じ通知に関する同期要求を確認と考える。]
[0031] オプションｂはより高速であり、オプションｂによる動作を図２に示す。] 図２
[0032] ＜動作例の表示＞
以下に図３に描くネットワーク例１０でリンク状態ハンドシェークプロトコルの動作を表示する。物理トポロジを提示するだけでなく、この物理トポロジ上に種々の転送トポロジが存在しうる。] 図３
[0033] トポロジ変化が発生したと仮定しよう。変化はあらゆる種類の変化でありうる；変化の種類は方法にとり問題ではないので、変化自体は図示しない。無指定の、事実上ランダム順序で変化に関してノード１２に通知する。ノード１２が変化に気づく順序は提案する本方法の動作では問題ではない。ある順序を一例として選択し、以下で説明する。]
[0034] 図４に示すように、ノードＢおよびＦが変化に気づいたと仮定する。] 図４
[0035] 図５が示すように、ノードＢおよびＦは、トポロジ変化に気づくと、それらのポートをブロックし、受信した通知に関する同期要求を送出する。] 図５
[0036] 図６に示すようにその後、ノードＡおよびＨも変化について通知を受ける。ノードＡおよびＨは同期要求を受信したポートで隣接ノードに同期確認を返送する。ノードＡおよびＨはそれらのポートとは異なる他の全てのポートをブロックし、同期要求を送出する。] 図６
[0037] 図７に描くように確認が届くと直ぐ、Ａ−ＢおよびＦ−Ｈリンクはブロック解除になる。ノードＣ、Ｄ、Ｅ、ＩおよびＪは次のステップで変化に気づき、従ってこれらのノードは前要求を確認、その残りのポートをブロックし、同期要求を送出する。なお、ノードＩおよびＪが同時に要求を送信し、要求の同時送信はノードＣおよびＥにも当てはまる。] 図７
[0038] 図１および図２に示すアルゴリズムを適用する、即ち両隣接ノードが同じリンクで同じ通知に対する要求を送信すれば、その場合両隣接ノードは他のノード側からの要求の受信後リンクをアクティブにする。図８は以前のメッセージの結果を示す。] 図１ 図２ 図８
[0039] 図９が示すのは、全ノード１２が更新し、最後の１つが確認を返送し、従ってブロックされたリンクが存在しない場合である。] 図９
[0040] 以上の図が示すように、収束過程で転送トポロジにおいて無関係の切断が存在し、これらの切断は相互に対し同期しないが、ネットワーク・ノード１２の通知順序に依存する。非常に重要であるのは、収束過程でネットワーク１０を閉鎖しないことである。ハンドシェーク技術がＲＳＴＰ／ＭＳＴＰに実装する技術と異なるのは、ＲＳＴＰ／ＭＳＴＰではハンドシェークは距離ベクトルにより伝達するトポロジ変化に関する情報伝搬と関連し、従って提案−合意ハンドシェークはルートブリッジからリーフブリッジへ向かうシーケンスに従わねばならないからである。]
[0041] ２、３の特定するシナリオが存在し、そのシナリオではループ軽減、例えば入力チェックを適用するにもかかわらずＳＰＢに対し提案されたＩＳ−ＩＳベース構成では過渡のループが発生しうる。シナリオの１つを図１０に描く。] 図１０
[0042] ＡとＢ間の物理接続を切断し、同時にＢとＥ間に新規物理接続が発生する。リンクコストも図に示す；矢印はノードＡからのパケット送信を示す。見て分かりうるように、初期および最終トポロジはループフリーである。ＡとＤ間のリンクは初期トポロジでは使用しない；ＣとＤ間のリンクは最終トポロジでは使用しない。しかしながらノードＡ、ＢおよびＥはトポロジに関して見解を更新するが、ノードＣおよびＤが古い見解を有すれば、過渡期にループを形成する。たとえ入力チェックを適用しても、ループは発生する。]
[0043] リンク状態ハンドシェーク技術の適用は図１１に描くようにネットワーク１０の偶発ループを防止する。] 図１１
[0044] ループが発生しえないのは、異なるトポロジ見解を有する隣接ノード間リンクを常に切断するからである。]
[0045] リンク状態ハンドシェーク技術は種々の方法で実装することができる。２つの実装可能性例をここで説明する。]
[0046] 複数のＩＳ−ＩＳＰＤＵの支援により、かつノード１２の各ポート毎に新規フラグの導入により、リンク状態ハンドシェーク機構を実装することができる。このフラグをブロック・フラグと称する。ここでは、複数の既存ＩＳ−ＩＳＰＤＵの適用について説明する。これに対する代替はハンドシェーク機構に複数の新規ＰＤＵまたは複数のＴＬＶを定義することである。]
[0047] ＩＳ−ＩＳでは、ポート（回線）毎に各リンク状態ＰＤＵ（ＬＳＰ）に設定することができる送信ルーティング・メッセージ・フラグ（ＳＲＭフラグ、Send Routing Message flag）により、複数のＬＳＰの送信を制御する。ポートのＬＳＰにＳＲＭフラグを設定すれば、その場合最小ＬＳＰ送信間隔の終了時にまたは新規ＬＳＰを受信すれば直ちに、ＬＳＰを送信しようとする。即ち、複数のＬＰＳを送出するのは、更新処理が自動的に複数のＬＰＳを再生成するからか、またはネットワークトポロジに関する新しい情報を含む新規ＬＳＰが着信したからの何れかであるからである。両種類のＬＳＰ送信はＳＲＭフラグにより制御する。ポイントツーポイントリンクでは部分シーケンス番号ＰＤＵ（ＰＳＮＰ、Partial Sequence Number PDU）または完全シーケンス番号ＰＤＵ（ＣＳＮＰ、Complete Sequence Number PDU）の何れかをそのポートのそのＬＳＰに関して受信すれば、ＳＲＭフラグを消去する。即ちＰＳＮＰが役立つのは、ＰＳＮＰにリストする複数のＬＳＰの一種の確認を隣接ノードにより受信した場合である。ＬＳＰをＰＳＮＰメッセージにリストしなければ、その場合ＳＲＭフラグは設定したまま残り、したがって、ＬＳＰをその隣接ノードに送信しようとする。即ちＰＳＮＰはポイントツーポイントリンクを経るＩＳ−ＩＳにおける複数のＬＳＰの再送信制御用である。]
[0048] リンク状態ハンドシェーク機構はＩＳ−ＩＳへの幾つかの拡張により実装することができる。各ポートに新規フラグ：ブロック・フラグを導入する；ブロック・フラグを設定すれば、その場合ユーザプレーンフレームはそのポートを介して通過することは認められず、設定しなければそのポートを介してユーザフレームを送信することができる。ポートブロックはともかく実装しなければならない、即ちフレームはそのポートを介してノード１２に入ることができず、フレームはそのポートを介して送出することができない。これを実装することができるのは、例えばブロック・フラグにより制御するフィルタの設定による。なお、ブリッジ・ネットワーク１０を経てＩＳ−ＩＳを使用すれば、その場合ＲＳＴＰ／ＭＳＴＰポートブロックの役割の使用によりポートブロックを実装することができる。同期要求メッセージとして複数のＬＳＰを使用し、リンク状態ハンドシェーク方法の同期確認メッセージとして複数のＰＳＮＰを使用する。これに加えて、ＰＳＮＰ間隔に従い送出する複数のＰＳＮＰ送信を加速しなければならない。ＩＳ−ＩＳの現適用では、ＰＳＮＰ間隔は数秒の範囲にあり、ＩＳ−ＩＳの現適用は非常に緩やかな収束になりうるので、これをループ防止方法に適用できない。したがって、ＰＳＮＰ間隔をミリ秒または数十ミリ秒の範囲に減じなければならない。複数のＰＳＮＰ送信を送信シーケンス番号メッセージ・フラグ（ＳＳＮフラグ、Send Sequence Numbers Message flags）により制御し、ＳＳＮフラグをポイントツーポイントリンクにおいて送信する各ＬＳＰの受信時に設定する。ポートのＬＳＰにＳＳＮフラグを設定すれば、その場合そのポートで送出する次ＰＳＮＰに対応ＬＳＰをリストしなければならない。対応ＰＳＮＰを送出するとＳＳＮフラグを消去する。複数のＰＳＮＰ送信を加速できるために、複数のＬＳＰのＳＳＮフラグを非常に容易にそして速くチェックできなければならない。したがって、提案するのは、ＳＳＮフラグの別のベクトル（ＳＳＮvector）の維持であり、その結果設定ＳＳＮフラグが存在し、対応ＬＳＰを次ＰＳＮＰにリストすべきであるかのバイナリ演算により、ＳＳＮフラグを容易にチェックすることができる。別の可能性はポーリングの種類のＰＳＮＰ間隔ベースの送信に代わり複数のＰＳＮＰ送信に中断ベースの制御を実装することである。ＰＳＮＰを受信すると、ＳＲＭフラグを消去する。その場合、両隣接ノードは対応ＬＳＰにより伝達するトポロジ変化に気づき、従って両隣接ノード間リンクをブロック解除することができる。即ちブロック・フラグは消去しなければならず、リンクは再アクティブ化する。]
[0049] これらの設定および拡張によるＩＳ−ＩＳ動作はポイントツーポイントリンクのみを設備するネットワーク１０では以下の通りである。ノード１２がそのポートの１つにおいてトポロジ変化に関するＬＳＰを受信すると仮定しよう。ＬＳＰを受信したポートを除く全ポートのそのＬＳＰに次いでＳＲＭフラグを設定する。ＬＳＰが以前のものの反復でなく、トポロジ変化に関するものであれば、その場合ＬＳＰが着信したポートを除く全ポートにブロック・フラグをまた設定しなければならない。即ちこれらのポートの全てをブロックしなければならない。なお、ＬＳＰが着信したポートをブロックする必要がないのは、そのノード１２がＬＳＰの着信したポートで情報を送信した場合その特定ノード１２に接続する隣接ノードがトポロジ変化に気づくためである。ＳＲＭフラグをポートに設定すれば、その場合そのポートを介してＩＳ−ＩＳエンティティはＬＳＰを転送する。そのポートでＰＳＮＰを受信するまで、ＳＲＭフラグは設定したままである。ポイントツーポイントリンクで隣接ノードがＬＳＰを受信すると、隣接ノードは対応ＳＳＮフラグを設定する。ＳＳＮフラグをＬＳＰに設定すれば、その場合ＰＳＮＰ間隔に従い周期的に送信する次ＰＳＮＰにおいてそのＬＳＰ受信を隣接ノードに報告しようとする。ＰＳＮＰ間隔内に受信する全ＬＳＰは同じＰＳＮＰにおいて確認する。ＰＳＮＰを受信すると、ＳＲＭフラグおよびブロック・フラグを共に消去し、リンクをブロック解除し、ユーザフレームをそのリンクで送信することができる。]
[0050] ＲＳＴＰ／ＭＳＴＰはループ防止の提案−合意ハンドシェーク機構を提供する。この機構はルートブリッジからの距離ベクトルに関連し、距離ベクトルは距離ベクトルが変化したとすればトポロジ変化情報を示す。ＲＳＴＰおよびＭＳＴＰは距離ベクトル制御プロトコルであるので、ＩＳ−ＩＳのようなリンク状態制御プロトコルと組み合わせるその適用は有益ではない。ＩＳ−ＩＳがＳＰＢにおけるアクティブトポロジ構成の制御プロトコルであれば、その場合ＲＳＴＰ／ＭＳＴＰは並列に動作すべきではない。]
[0051] しかしながらＩＳ−ＩＳはブリッジ・ネットワーク１０においてアクティブトポロジ構成に使用することができ、リンク状態ハンドシェーク機構をＲＳＴＰ／ＭＳＴＰの複数のＢＰＤＵに実装し、ＩＳ−ＩＳと並列に動作することができる。]
[0052] ＲＳＴＰ／ＭＳＴＰＢの複数のＰＤＵはハンドシェーク機構を実装し、従ってリンク状態ハンドシェーク機構は自体の若干の修正によりこのような複数のＢＰＤＵに実装することができる。]
[0053] 複数のＢＰＤＵの提案フラグ（オクテット５のビット２）は同期要求メッセージのフラグとして使用することができる。]
[0054] 複数のＢＰＤＵの合意フラグ（オクテット５のビット７）は同期確認メッセージのフラグとして使用することができる。]
[0055] ＩＳ−ＩＳが目的とするのは、ＳＰＢのリンク状態制御プロトコルとしてＳＰＢにおいて使用することである。ＩＳ−ＩＳＬＳＰのＬＳＰＩＤおよびシーケンス番号はトポロジ変化情報の特定情報として使用することができる。ＬＳＰＩＤはリンク状態ＰＤＵの送信元のシステムＩＤである；シーケンス番号はＬＳＰのシーケンス番号である。したがって、ＬＳＰＩＤおよびシーケンス番号を複数のＢＰＤＵに組み込み、提案するリンク状態ハンドシェーク機構の同期要求および同期確認メッセージを実装すべきである。同じＢＰＤＵにおいてより多くの複数のＬＳＰ特定情報を形成する余地を定義するのはオプションである。これに対する代替はトポロジ・データベースのダイジェスト情報により複数のＢＰＤＵを拡張し、ダイジェスト情報に基づきハンドシェークを提供することである。]
[0056] ポートブロックは例えばポートブロックの役割の使用により実装することができる。]
[0057] 即ちループ防止技術をＲＳＴＰ／ＭＳＴＰの複数のＢＰＤＵに基づき容易に実装することができる。]
[0058] 本発明が提供するのは、リンク状態制御プロトコルによって制御されるネットワーク１０における新しいループ防止方法である。リンク状態プロトコルはネットワーク１０のトポロジに関するその見解を非同期に、即ち予測不可能な順序で更新する；したがって、トポロジの変化の後、ネットワーク１０の収束過程で過渡のループが発生しえ、これがネットワーク１０の性能を悪化させうる。提案するリンク状態ハンドシェーク方法は隣接ノード２０間への一時的切断の導入によりネットワーク１０におけるループの発生を防止する。これらの切断は相互に依存せず、従って好適な実装および構成により収束時間に大きく影響を及ぼさない。２つの実装の可能性をまた提案した。]
[0059] 本発明はＩＥＥＥ８０２．１ａｑ最短経路ブリッジングにおいて進行中の考察に関係する。本発明はＩＰ高速再ルーティングフレームワークにおいても適用できる。]
[0060] 説明のために以上の実施形態において詳細に本発明を説明したが、そのような詳細が、ただ本発明が以下の特許請求の範囲により記載するであろう目的および変形を除き、本発明の精神と範囲を逸脱することなくその範囲において当業者によりなし得るその目的およびその変形のためであることを理解すべきである。]
[0061] ＜略語の説明＞
ＢＰＤＵブリッジ・プロトコル・データ・ユニット
ＣＳＮＰ 完全シーケンス番号ＰＤＵ
ＩＰ−ＦＲＲＩＰ高速再ルーティング
ＩＳ−ＩＳ中間システム間ルーティングプロトコル
ＬＳＡリンク状態通知
ＬＳＰリンク状態プロトコル・データ・ユニット
ＭＳＴＰマルチプル・スパニング・ツリー・プロトコル
ＯＳＰＦオープン最短経路ファースト
ＰＳＮＰ部分シーケンス番号ＰＤＵ
ＲＳＴＰ 高速スパニング・ツリー・プロトコル
ＳＰＢ 最短経路ブリッジング
ＳＲＭflag 送信ルーティング・メッセージ・フラグ
ＳＳＮflag送信シーケンス番号メッセージ・フラグ]

权利要求:

請求項1
リンク状態プロトコルによって制御される複数のネットワーク・ノードを有するネットワークのネットワーク・ノードにおける過渡のループを防止する方法であって、前記ネットワークのトポロジの変化に関する情報を含むメッセージをネットワーク・インタフェースで受信する受信ステップと、処理ユニットによって、前記ネットワークの各隣接ノードへのトラフィックの転送を、前記ネットワーク・インタフェースでブロックするブロックステップと、前記処理ユニットによって、トポロジの前記変化に関して各隣接ノードと合意する合意ステップと、メモリに格納された前記トポロジについての情報と同じトポロジについての情報を隣接ノードが有する場合に、前記トラフィックの転送のブロックを解除する解除ステップとを含むことを特徴とする方法。
請求項2
前記受信ステップは、前記トポロジの前記変化に関する情報を含む通知を、前記ネットワーク・インタフェースで他の隣接ノードから受信するステップを含むことを特徴とする請求項１に記載の方法。
請求項3
前記ブロックステップは、前記変化によって影響を受ける、少なくともアクティブトポロジ又は転送経路を、前記ネットワーク・インタフェースでブロックするステップを含むことを特徴とする請求項２に記載の方法。
請求項4
前記隣接ノードが、前記メモリに格納されたトポロジと、該隣接ノードのメモリに格納されたトポロジとが同じになることを合意するまで前記ブロックを維持する維持ステップをさらに含むことを特徴とする請求項３に記載の方法。
請求項5
前記合意ステップは、前記通知の前記情報を含む同期要求を、少なくとも１つのポートで前記他の隣接ノードに送信するステップを含むことを特徴とする請求項４に記載の方法。
請求項6
前記合意ステップは、前記隣接ノードが同じ通知を受信したか、即ち、同じトポロジ・データベースを有するかどうかを検証する検証ステップを含むことを特徴とする請求項５に記載の方法。
請求項7
前記検証ステップは、前記同期要求が送信された前記隣接ノードから、前記隣接ノードが前記通知のトポロジ情報に従って前記トポロジを更新したことを示す同期確認を受信するステップを含むことを特徴とする請求項６に記載の方法。
請求項8
前記同期確認を受信する前記ステップは、前記通知のノードＩＤ及びシーケンス番号を有する前記同期確認を受信するステップを含むことを特徴とする請求項７に記載の方法。
請求項9
前記ネットワーク・インタフェースで同期要求を受信するステップをさらに含むことを特徴とする請求項３に記載の方法。
請求項10
前記処理ユニットで、前記通知が受信され、かつ、該通知に関する同期要求が送信されるように処理されたかどうかを検証するステップをさらに含むことを特徴とする請求項９に記載の方法。
請求項11
前記ネットワーク・インタフェースで、同期確認を送信するステップをさらに含むことを特徴とする請求項１０に記載の方法。
請求項12
ポートごとのＩＳ−ＩＳリンク状態ＰＤＵにおける送信ルーティング・メッセージ・フラグを設定するステップと、前記通知がトポロジ変化情報を含む場合にポートのブロックに関するフラグを設定するステップと、部分シーケンス番号プロトコル・データ・ユニット（ＰＳＮＰ）の受信に応じて、ポートのブロックに関する前記フラグをクリアするステップと、より早い集束のために、ミリ秒の範囲で前記ＰＳＮＰの間隔を構成するステップとをさらに含むことを特徴とする請求項８に記載の方法。
請求項13
ＲＳＴＰ／ＭＳＴＰのＢＰＤＵは、同期要求メッセージのためのフラグと、同期確認メッセージのためのフラグとを有し、前記ＢＰＤＵは、前記トポロジ・データベース上の記述、又は、前記トポロジ・データベースのダイジェスト情報の何れかを含むことを特徴とする請求項８に記載の方法。
請求項14
前記合意ステップは、前記メモリ格納された前記トポロジの少なくとも一部のダイジェスト情報について前記隣接ノードと合意するステップを含み、前記ダイジェスト情報は、前記トポロジ・データベースのＣＲＣ又はハッシュであることを特徴とする請求項４に記載の方法。
請求項15
リンク状態プロトコルによって制御される通信ネットワークのネットワーク・ノードであって、前記ネットワークのトポロジの変化に関する情報を含むメッセージを受信するネットワーク・インタフェースと、前記ネットワークの少なくとも１つの隣接ノードへのトラフィックの転送を前記ネットワーク・インタフェースでブロックし、トポロジの前記変化について前記隣接ノードと合意し、前記隣接ノードが、メモリに格納された前記トポロジについての情報と同じトポロジについての情報を有する場合に、前記トラフィックの転送のブロックを解除する処理ユニットとを備えることを特徴とするネットワーク・ノード。
請求項16
前記ネットワーク・インタフェースは、前記トポロジの変化に関する情報を含む通知を他の隣接ノードから受信することを特徴とする請求項１５に記載のネットワーク・ノード。
請求項17
前記処理ユニットは、前記変化によって影響を受ける、少なくともアクティブトポロジ又は転送経路を、前記ネットワーク・インタフェースの少なくとも１つのポートでブロックすることを特徴とする請求項１６に記載のネットワーク・ノード。
請求項18
前記ネットワーク・インタフェースは、前記通知の前記情報を含む同期要求を、少なくとも１つのポートで前記隣接ノードに送信することを特徴とする請求項１７に記載のネットワーク・ノード。
請求項19
前記処理ユニットは、前記隣接ノードが前記通知の前記情報を有するかどうかを検証することを特徴とする請求項１８に記載のネットワーク・ノード。
請求項20
前記ネットワーク・インタフェースは、前記同期要求が送信された前記隣接ノードから、前記隣接ノードが前記通知のトポロジ情報に従って前記トポロジを更新したことを示す同期確認を受信することを特徴とする請求項１９に記載のネットワーク・ノード。
請求項21
前記ネットワーク・インタフェースは、前記通知のノードＩＤ及びシーケンス番号を有する前記同期確認を受信することを特徴とする請求項２０に記載のネットワーク・ノード。
請求項22
前記ネットワーク・インタフェースは、同期要求を受信することを特徴とする請求項２１に記載のネットワーク・ノード。
請求項23
前記処理ユニットは、前記通知が受信され、かつ、該通知に関する同期要求が送信されるように処理されたかどうかを検証することを特徴とする請求項２２に記載のネットワーク・ノード。
請求項24
前記ネットワーク・インタフェースは、同期確認を送信することを特徴とする請求項２３に記載のネットワーク・ノード。
請求項25
送信ルーティング・メッセージ・フラグが、ポートごとのリンク状態ＰＤＵにおけるネットワーク・インタフェースで設定され、前記ネットワーク・インタフェースは、ポートのブロックに関するフラグを維持し、前記通知がトポロジ変化情報を含む場合にポートのブロックに関する前記フラグを設定し、対応する部分シーケンス番号プロトコル・データ・ユニットの受信に応じて、ポートのブロックに関する前記フラグをクリアすることを特徴とする請求項２４に記載のネットワーク・ノード。
請求項26
ＲＳＴＰ／ＭＳＴＰのＢＰＤＵは、同期要求メッセージのためのフラグと、同期確認メッセージのためのフラグとを有し、前記ＢＰＤＵは、前記トポロジ・データベース上の記述、又は、前記トポロジ・データベースのダイジェスト情報の何れかを含むことを特徴とする請求項２４に記載のネットワーク・ノード。